/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a binary tree, flatten it to a linked list in-place.
 * 
 *              For example, Given
 * 
 *              		1 
 *                     / \ 
 *                    2   5 
 *                   / \   \ 
 *                  3   4   6 
 *              
 *              The flattened tree should look like: 
 *              	1 
 *              	 \ 
 *              	  2
 *              	   \ 
 *              	    3 
 *              	     \ 
 *              	      4 
 *              	       \ 
 *              			5 
 *              			 \ 
 *              		 	  6
 */
public class FlattenBinaryTreeToLinkedList {

	private class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	// recursive version
	// can also use a stack, non-recursive version
	public void flatten(TreeNode root) {
		if (null == root)
			return;

		TreeNode left = root.left;
		TreeNode right = root.right;
		root.left = null;
		root.right = null;
		flatten(left);
		flatten(right);
		root.right = left;

		TreeNode pre = root;
		while (pre.right != null) {
			pre = pre.right;
		}
		pre.right = right;
	}

	@Test
	public void test() {
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		TreeNode n6 = new TreeNode(6);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n4.left = n5;
		n4.right = n6;

		flatten(n1);

		TreeNode node = n1;
		while (node != null) {
			System.out.println(node.val);
			node = node.right;
		}
	}
}
